package alo.p3.work;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @ClassName NextLargerNodes
 * @Description 寻找最近的一个较大数，返回int[]
 * @Author Fanxc
 * @DATE 2020/11/29 0029 17:03
 * @Version 1.0
 */
public class NextLargerNodes {
    /**
     * @Author Fanxc
     * @Description //链表结点的基本类
     * @Date 2020/11/29 0029 17:05
     * @Param
     * @return
     **/

    class ListNode{
        int val;
        ListNode next;
        ListNode(int data){
            this.val=data;
        }
    }

    class Solution{
        /**
         * @Author Fanxc
         * @Description //TODO
         * @Date 2020/11/29 0029 17:08
         * @Param [head]
         * @return int[]
         **/

        public int[] nextLargerNodes(ListNode head){
            List<Integer> list=new ArrayList<>();
            Stack<Integer> stack=new Stack<>();
            for (ListNode node=head;node!=null;node=node.next){
                while (!stack.isEmpty()&&node.val>list.get(stack.peek())){
                    list.set(stack.pop(), node.val);
                }
                stack.push(list.size());
                list.add(node.val);

            }
            for (int i : stack) {
                list.set(i, 0);
            }
            int[] res = new int[list.size()];
            for (int i = 0; i < res.length; i++) {
                res[i] = list.get(i);
            }
            return res;
        }
    }
}
